package oj;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LC207 {
    //存储有向图
    List<List<Integer>> list;
    //存储每个节点的入度
    int[] edges;
    //存储答案

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        list=new ArrayList<List<Integer>>();
        for(int i=0;i<numCourses;i++){
            list.add(new ArrayList<Integer>());
        }
        edges=new int[numCourses];
        for(int[] info:prerequisites){
            list.get(info[1]).add(info[0]);
            ++edges[info[0]];
        }
        Queue<Integer> q=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(edges[i]==0) q.offer(i);
        }
        int visited =0;
        while(!q.isEmpty()){
            visited++;
            int u=q.poll();
            for(int v:list.get(u)){
                --edges[v];
                if(edges[v]==0){
                    q.offer(v);
                }
            }
        }
        return visited==numCourses;
    }
}
